//
//  SList.c
//  单链表
//
//  Created by 卜绎皓 on 2022/5/24.
//

#include "SList.h"

//单链表的遍历
void SListPrint(SListNode* phead)
{
    //不用assert
    //因为它完全就是有可能为空的
    SListNode* cur = phead;
    while (cur != NULL)
    {
        printf("%d-->", cur->data);
        cur = cur->next;//这里的next是下一个节点的地址
        //这里不能够是cur++;因为链表结点地址不连续
        //但是我们的指针域里面存了下一个结点的地址，我们直接
        //cur=cur->next;
    }
    //以前顺序表其实就是数组，我们挨个挨个，用循环就可以打印了
    //但是这里不一样，这里是链表，串起来的
    //地址不一定连续
    printf("NULL\n");//这样可以美化一下
}

//开辟节点接口
SListNode* BuySListNode(SListDataType x) {
    SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));//开一个结点
    if (newNode == NULL) {
        printf("申请结点失败\n");
        exit(-1);
    }
    newNode->data = x;
    newNode->next = NULL;//一开始我们先把新结点的next置空
                         //但如果是中间插入或者头插的话，在接口外头我们还要把这个next指向后面的结点
    return newNode;
}

//尾插接口
void SListPushBack(SListNode** pphead, SListDataType x) {
    //这里怎么尾插
    //我们要和顺序表区分开来
    //我们是直接把data插进去吗，插到哪里去，有空间插吗
    //链表的特点是按需索取
    //我们是要先开辟一个空间，放好data，把它放到最后一个结点的后面
    //无论链表为空还是不为空，一上来都要创建一个结点
    SListNode* newNode = BuySListNode(x);

    if (*pphead == NULL) {
        //这种情况，我们要先开一个结点
        //所以我们开结点的过程直接定义成一个接口
        *pphead = newNode;
    }
    else {
        //找尾---遍历
        SListNode* tail = *pphead;
        while (tail->next != NULL) {
            tail = tail->next;//不为空继续往下走
        }
        //对于链表而言
        //不需要扩容这些东西
        //按需索取
        //对于申请内存来说，顺序表比链表好
        tail->next = newNode;//把新结点地址给tail->next即可
    }
}

//尾删接口
void SListPopBack(SListNode** pphead) {
    //1.空
    //2.一个
    //3.一个以上
    //1.
    if (*pphead == NULL) {
        return;
    }
    //2.
    else if ((*pphead)->next == NULL) {
        free(*pphead);
        *pphead = NULL;//记得置空
    }
    //3.
    else {
        //关键：把前一个的next置空
        SListNode* tail = *pphead;
        //prev:前一个结点
        SListNode* prev = NULL;
        while (tail->next != NULL) {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        prev->next = NULL;//不要忘记将前一个结点的next置空
    }
}

//头插接口
void SListPushFront(SListNode** pphead, SListDataType x) {
    SListNode* newnode = BuySListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;//记得更改头指针的位置
}

//头删接口
void SListPopFront(SListNode** pphead) {
    //1.空
    //2.一个结点
    //3.一个以上的结点
    if (*pphead == NULL) {
        return;
    }
    else {
        //怎么删呢？
        //1.先free掉第一个-->不行：找不到下一个了
        //2.先让pList指向下一个--->不行：找不到我们要free的那个了
        //正确的做法：先让一个临时指针充当next的作用，free掉，再让pList指向临时next的位置
        //或者用临时指针保存我们要free的，pList先走也可以

        //此时我们发现，我们这个代码也可以处理只有一个结点的情况，所以第二种第三种情况合并
        SListNode* next = (*pphead)->next;
        free(*pphead);
        *pphead = next;
    }
}

//查找接口
SListNode* SListFind(SListNode* phead, SListDataType x) {
    SListNode* cur = phead;
    while (cur != NULL) {//遍历过程
        if (cur->data == x) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;//循环走完找不到，返回空指针
}

//删除pos位置后的节点
void SListEraseAfter(SListNode* pos) {
    assert(pos);
    if (pos->next) {
        //pos->next=pos->next->next;
        //不推荐这种写法，这样一些我们原来的pos->next就不见了
        SListNode* next = pos->next;
        SListNode* next_next = next->next;
        pos->next = next_next;
        free(next);
    }
}

//在pos位置插入节点
void SListInsertAfter(SListNode* pos, SListDataType x) {
    assert(pos);//这里是要断言的,因为给的pos不能为空
    SListNode* newnode = BuySListNode(x);
    newnode->next = pos->next;//先把后面的地址给新结点，再将前一个的next改成新结点地址
    pos->next = newnode;
}


